package com.example.algorithm;

import java.nio.charset.StandardCharsets;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * BFS获取每个零售店到最近仓库最短距离，并输出距离之和
 *
 * @DATE 2024/6/23
 **/
public class BFS2 {

    // 0仓库，-1障碍，1零售店
    // 无法到达仓库的零售店不参与计算
    // 没有零售店或者没有仓库，则返回0
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name());
        int rows = cin.nextInt();
        int cols = cin.nextInt();
        int[][] grids = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grids[i][j] = cin.nextInt();
            }
        }
        cin.close();
        System.out.println(nearestWareHouse(grids));
    }

    static class Point {

        int x;
        int y;
        int step;

        public Point(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }

    private static int nearestWareHouse(int[][] grid) {
        int result = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<Point> queue = new LinkedList<>();
        // 遍历grid，把所有仓库节点坐标放入bfs队列
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0) {
                    // 如果是仓库节点，入队
                    queue.add(new Point(i, j, 0));
                }
            }
        }

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int x = point.x;
            int y = point.y;
            // 左
            if (x != 0 && grid[x - 1][y] == 1) {
                queue.add(new Point(x - 1, y, point.step + 1));
                grid[x - 1][y] = -1;
            }
            // 右
            if (x != rows - 1 && grid[x + 1][y] == 1) {
                queue.add(new Point(x + 1, y, point.step + 1));
                grid[x + 1][y] = -1;
            }
            // 上
            if (y != 0 && grid[x][y - 1] == 1) {
                queue.add(new Point(x + 1, y, point.step + 1));
                grid[x + 1][y] = -1;
            }
            // 下
            if (y != cols - 1 && grid[x][y + 1] == 1) {
                queue.add(new Point(x, y + 1, point.step + 1));
                grid[x][y + 1] = -1;
            }
            result += point.step;
        }
        return result;
    }
}
